//
//  Graph_bfs.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/15.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension GraphMatrix {
    
    /// breath-first search
    /// 广度优先遍历算法
    /// 这种算法本质上是对树层次遍历的推广
    public func bfs(startAt index: Int, clock: inout Int) {
        
        let queue = Queue<Int>()
        /// wtf?! swift并不支持函数返回引用
        // 更新状态 从undiscovered -> discovered
        vertexes[index].status = .discovered
        queue.enqueue(index)
     
        while !queue.isEmpty {
            // 取队首
            let index = queue.dequeue()!
            // 记录时间节点
            clock += 1
            vertexes[index].dTime = clock
            // 考察位于index处顶点的所有邻居
            var vertexIdx = firstNbr(at: index)
            while vertexIdx > -1 {
                // 若位于vertexIdx的顶点尚未被发现
                if vertexes[vertexIdx].status == .undiscovered {
                    // 则更新其状态 并加入队列
                    vertexes[vertexIdx].status = .discovered
                    queue.enqueue(vertexIdx)
                    // 引入树的层次结构
                    edges[index][vertexIdx]?.type = .tree
                    vertexes[vertexIdx].parent = index
                } else { // 若位于vertexIdx的顶点已被发现或已被访问 则跳过
                    edges[index][vertexIdx]?.type = .cross
                }
                // 转向下一个邻接顶点
                vertexIdx = nextNbr(at: index, relativeTo: vertexIdx)
            }
            // 位于index访问完毕
            vertexes[index].status = .visited
        }
    }
}
